/*
 * @Author: szx
 * @Date: 2021-11-03 16:43:24
 * @LastEditTime: 2021-11-03 17:24:58
 * @Description:
 * @FilePath: \leetcode\1-99\42\42.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
// 暴力法，超时
// class Solution {
//    public:
//     int trap(vector<int>& height) {
//         int ans = 0;
//         int size = height.size();
//         for (int i = 1; i < size - 1; i++) {
//             int max_left = 0, max_right = 0;
//             for (int j = i; j >= 0; j--) {
//                 max_left = max(max_left, height[j]);
//             }
//             for (int j = i; j < size; j++) {
//                 max_right = max(max_right, height[j]);
//             }
//             ans += min(max_left, max_right) - height[i];
//         }
//         return ans;
//     }
// };


// 动态规划法，这个挺好理解，先遍历一遍，存储每个点左边和右边。
// class Solution {
// public:
//     int trap(vector<int>& height) {
//         int n = height.size();
//         if (n == 0) {
//             return 0;
//         }
//         vector<int> leftMax(n);
//         leftMax[0] = height[0];
//         for (int i = 1; i < n; ++i) {
//             leftMax[i] = max(leftMax[i - 1], height[i]);
//         }

//         vector<int> rightMax(n);
//         rightMax[n - 1] = height[n - 1];
//         for (int i = n - 2; i >= 0; --i) {
//             rightMax[i] = max(rightMax[i + 1], height[i]);
//         }

//         int ans = 0;
//         for (int i = 0; i < n; ++i) {
//             ans += min(leftMax[i], rightMax[i]) - height[i];
//         }
//         return ans;
//     }
// };

// 双指针 妙蛙种子都没这么妙好吧
// 如果左边比右边小，那么说明只能会被左边所限制，那么就去找左边的最大值，   
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};
